import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;

/*
 * @lc app=leetcode.cn id=692 lang=java
 *
 * [692] 前K个高频单词
 */

// @lc code=start
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> mp = new HashMap<>();
        for(String word : words){
            mp.put(word, mp.getOrDefault(word, 0)+1);
        }
        //因为最后只要string，所以根据int值对String排序即可,小根堆，堆大小为k。
        PriorityQueue<String> queue = new PriorityQueue<>(k,(o1, o2) -> {
            Integer o1Count = mp.get(o1);
            Integer o2Count = mp.get(o2);
            if(o1Count.equals(o2Count)){
                return o2.compareTo(o1);//o2>o1返回正值，表示要调整顺序，则字典序大的在前。
            }else{
                return o1Count-o2Count;//为负值表示不用调整顺序
            }
        });//优先按int值从小到大排，如果一样就是按String的字典序从大到小牌

        for(String word : mp.keySet()){//从String里选
            queue.offer(word);//注意这里插入后如果大于initialCapability，是会动态增长的。
            if(queue.size()>k){
                queue.poll();
            }
        }
        //它要求返回List，所以要把PriorityQueue改成List
        //所以上面要用小根堆，这样反过来之后,堆底的元素是int值最小的，堆顶是Int值最大的，int值相等时按字典序从小到大排了。
        LinkedList<String> stack = new LinkedList<>();
        while(!queue.isEmpty()){
            stack.push(queue.poll());
        }
        
        return stack;
    }
}
// @lc code=end

